package algocasts;

public class P10_pow {
    // 暴力法，N次循环
    public double pow(double x, int n) {
        double result = 1;
        long N = Math.abs((long) n);
        for (long i = 0; i < N; i++) {
            result *= x;
        }
        return (n < 0 ? 1 / result : result);
    }

    // Time: O(log n) Space: O(1)
    public double powFast(double x, int n) {
        double result = 1;
        long N = Math.abs((long) n);
        while (N != 0) {
            // N的底数为 1，则结果乘以当前的底数
            if ((N & 1) == 1) result *= x;
            x *= x; // 底数自乘
            N >>= 1;    // N 右移一位
        }
        return (n < 0 ? 1 / result : result);
    }

    public static void main(String[] args) {
        P10_pow solution = new P10_pow();
        System.out.println(solution.pow(-10.0, 3));
        System.out.println(solution.powFast(-10.0, 3));
    }
}
